Predicting Communications Bottlenecks
by Stathis Papaefstathiou

Listing One
const int Nproc = 16; // # of PCs
const int LperG = 4;  // Links per switch group
const int SwitchLinks = 32; // Links per switch
const int LevelLinks = 16; // Links between switches
int S1toS2[16]; // 1st switch -> 2nd switch mapping

// Initialize routing algorithm
void RoutingInit(void)
{
  // Determine static S1->S2 level connections
  for( int i = 0; i < LevelLinks; i++ )
  S1toS2[i] = (int)floor(((float)rand()/(RAND_MAX+1)) * LperG)+1;
}
// Create Routing Array for message Psrc -> Ptrg
void Routing(int Psrc,int Pdst, unsigned int (*Vr)[2])
{
  int SrcGr = Psrc/LperG;  // Src switch group
  int TrgGr = Pdst/LperG;  // Trg switch group
  // Initialise RA to zeros
  for( int i = 0; i < SwitchLinks; i++ )
  Vr[i][0] = Vr[i][1] = 0;
  // Routing
  Vr[Psrc][0] = 1;  // Psrc -> 1st level switch
  // If Ptrg && Pdst don't belong to same switch
  // involve 2nd level switch
  if( SrcGr != TrgGr ) {
  // Use static map to select 2nd level switch
  int selsw = S1toS2[Psrc];
  Vr[ SrcGr*LperG + selsw + LevelLinks-1][0] = 1;
  // Set busy link from 2nd-level switch to target proc 1st-level switch
  Vr[selsw + TrgGr * LperG + LevelLinks-1][1] = 1;
  }
  Vr[Pdst][1] = 1;  // 1nd level switch -> Ptrg
}


Listing Two
// Linear Regression Model
// Arguments
// n - number of measurements
// l - Message length array
// t - Communication delay array
// b0 - (returned) regression parameter
// b1 - (returned) regression parameter
//
// Tcom(len) = b0 + b1 * len
//
void lreg(int n,long* l,long* t,double& b0,double& b1)
{
 double mx,my,sxy,sx2;
 mx = my = sxy = sx2 = 0.0;
 for( int i = 0; i < n; i++ ) {
  mx += l[i]; my += t[i];
  sxy += l[i]*t[i];
  sx2 += pow(l[i],2.0);
 }
 mx = mx / n; my = my / n;

 b1 = (sxy-n*mx*my) / (sx2-n*pow(mx,2.0));
 b0 = my - b1 * mx;
}


Listing Three
// Workload customization class
class workload {
public:
  enum trace {  // Tracetype
  TRACE_IDLE,// Processor is idle
  TRACE_SCOM,// Synchronous communication
  TRACE_END // End of traces
  };
  // Print workload debug info
  virtual void  print(std::ostream&) = 0;
  // Get type of trace
  virtual trace  GetTraceType(int procid) = 0;
  // Get comm trace data
  virtual void  GetTraceData(int procid,int &src, int &trg,long &len) = 0;
  // Get idle processor trace data
  virtual void  GetTraceData(int procid, long &time) = 0;
  // Fetch next trace
  virtual trace  FetchNextTrace(int procid) = 0;
};


Listing Four
// Network customization class
class netsys {
 public:
  // Create Routing Array
  virtual void  Routing(int,int,unsigned char(*)[2]) = 0;
  // Return number of network links
  virtual int  GetLinkNo(void) = 0;
  // Return number of nodes connected
  virtual int  GetNproc(void) = 0;
  // Return size of packet in bytes
  virtual int  PacketSize(void) = 0;
  // Return network name
virtual const char* Name(void) = 0;
  // Return background load array
  virtual float (*GetBgrLoad(long clock))[2] = 0;
  // Return communication cost for quiet network
virtual long  Tcom(int hops,float packets) = 0;
// Inverse for Tcom for calculating packing consumed
// during an Event Horizon
virtual float T2Pack(long eh,int hops, float total_packets,
  float remaining_packets,long Tcom) = 0;
};


Listing Five
// Ouput trace customization class
class otrace {
 public:
  // Signal from evaleng -> otrace
  enum otrace_sig {
  CONFIG,GO_INIT,GO_STARTEVENT,
  GO_END,CREATEEVENT,NEWSCOM,
  NEWPROC,SYSCONT,MSGCONT,
  COMMCOST,EVENTHORIZON,
  UPPR_PROC,UPPR_SCOM,UPPR_PCNS,
  UPPR_END
  };
  // Receive output trace signal and arguments for evaluation engine
  virtual void  RecvSignal(otrace_sig ...)=0;
};


Listing Six
#include <iostream>
#include <fstream>
#include "ccmod.h"
#include "wrkascii.h"
#include "myrinet.h"
#include "otrdeb.h"

using namespace std;
int main(int argc,char** argv)
{
  const int Nproc = 16; // Number of PC nodes
  if( argc != 3 ) {
  cerr << "Usage: model.exe <workload traces> <output file>" << endl;
  return 1;
  }
  // Set up trace source if present
  ifstream fsrc(argv[1]);
  if( !fsrc ) {
  cerr << "Error opening trace file\n";
  return 1;
  }
  // Set up otrace file
  ofstream otrg(argv[2]);
  if( !otrg ) {
  cerr << "Error opening output trace file\n";
  return 1;
  }
  // Set up & evaluate model
  try {
  // Set up user defined classes
  // Ascii traces (derived from workload)
  wrkascii w(Nproc,1,&fsrc);

  // Network model (derived from netsys)
  myrinet myrswitch(Nproc);

  // Output trace facility (derived from otrace)
  // Use DBNONE to turn off debug mode
  otrdeb odb(otrdeb::DBALL,&otrg);

  // Set up evaluation engine
  evaleng e(&w,&myrswitch,&odb);
  // Evaluate
  // Return PC node clock
  cout << e.Go() << endl;
  }
  // Error exception
  catch( ccmod_error er ) {
  cerr << er.what() << endl;
  return(1);
  }
  return(0);
}


Listing Seven
// Inverse Exponential Distribution
static inline _ExpD(long l, long b)
{
 float inv = -l * log((float)rand()/(RAND_MAX+1));
 return( inv >= b ? 1 : inv/b);
}
// Function derives from netsys::GetBgrLoad
// Return background load vector based on exponential distribution
float (*ethernet::GetBgrLoad(long clock))[2]
{
  // Configure these parameters for your system
  // l - Measured average background load (packets/sec)
  // b - Max link bandwidth (packets/sec)
  const long l = 7000;
  const long b = 25000;
  // For each link
  for(int i = 0; i < GetLinkNo(); i++) {
 Vbgr[i][0] = _ExpD(l,b);
 Vbgr[i][1] = _ExpD(l,b);
  }
  return(Vbgr);
}